package review;

import java.util.TreeSet;

public class LeetCode_day8_review {
	
	/**
	 * Analysis:
	 * original position (x,y)-> new position (x',y')
	 * Each layer act as a circle
	 * @param image
	 */
	public static void rotateImage(int[][] image){
		if(image == null) return;
		int n = image.length;
		int layer = n/2;//number of layer
		for(int i = 0 ; i < layer ; i++){
			//for each layer
			for(int j = i ; j < n-i ; j++){
				int t = image[i][j];
				image[i][j] = image[n-i-1][j];
				image[n-i-1][j] = image[n-1-i][n-1-i];
				image[n-1-i][n-1-i] = image[i][n-1-i];
				image[i][n-1-i] = t;
				/*int temp = image[n-i-1][i];
				image[n-i-1][i] = image[i][j];
				int temp1 = image[n-i-1][n-i-1];
				image[n-i-1][n-i-1] = temp;
				temp = image[i][n-i-1];
				image[i][n-i-1] = temp1;
				image[i][j] = temp;//*/
			}
		}
		
	}
	/**
	 * [解题思路]
	 * 对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
	 * 1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
	 * 2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
	 * 3. 再扫描一遍，求取容积并加和。
	 * #2和#3可以合并成一个循环，
	 * @param a
	 * @return
	 */
	public static int trappingRainWater(int[] a){
		if(a == null) return -1;
		int[] leftMax = new int[a.length];
		int[] rightMax = new int[a.length];
		int left = a[0], right = a[a.length-1];
		for(int i = 0 ; i < a.length ; i++){
			//store left max
			if(i > 0){
				leftMax[i] = left;
				if(a[i] > left) left = a[i];
			}
			//store right max
			int ind = a.length - i - 1;
			if(ind < a.length-1){
				rightMax[ind] = right;
				if(a[ind] > right) right = a[ind];
			}
		}
		
		int sum = 0;
		for(int i = 1 ; i < a.length-1 ; i++){
			int height = Math.min(leftMax[i], rightMax[i]);
			if(height > a[i]) sum += height - a[i];
		}
		return sum;
	}

	/**
	 * http://gongxuns.blogspot.com/2012/12/leetcode-reverse-nodes-in-k-group.html
	 * @param head
	 * @param k
	 * @return
	 */
	public static ListNode reverseNodesInKGroup(ListNode head, int k){
		return null;
	}
	public static int divide(int a, int b){
		if(a < b) return 0;
		
		int temp = b, res = 1;
		while(temp < a) {
			temp = temp << 1;
			res  = res << 1;
		}
		res = res >> 1;
		temp = temp >> 1;
		res += divide(a-temp, b);
		
		return res;
	}
	
	/**
	 * 1) Segregate positive numbers from others i.e., move all non-positive numbers to left side. 
	 * In the following code, segregate() function does this part.
	 * 2) Now we can ignore non-positive elements and consider only the part 
	 * of array which contains all positive elements. 
	 * We traverse the array containing all positive numbers and to mark presence 
	 * of an element x, we change the sign of value at index x to negative. 
	 * We traverse the array again and print the first index which has positive value.
	 * In the following code, findMissingPositive() function does this part. 
	 * Note that in findMissingPositive, we have subtracted 1 from the values as 
	 * indexes start from 0 in C.
	 * @param a
	 * @return
	 */
	
	public static int firstMissingPositive(int[] a){
		if(a == null) return -1;
		//move all non-positive number to the left side of the array
		int pos = 0;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] <= 0){
				a[i] = a[i] ^ a[pos];
				a[pos] = a[i] ^ a[pos];
				a[i] = a[i] ^ a[pos];
				pos++;
			}
		
		for(int i = pos ; i < a.length ; i++){
			int temp = Math.abs(a[i])+pos;
			if(temp-1 < a.length && a[temp-1] > 0)
				a[temp-1] = -a[temp-1];
		}
		
		for(int i = pos ; i < a.length ; i++){
			if(a[i] > 0)
				return i-pos+1;
		}
		return a.length+1;
	}
	
	public static int firstMissingPositive(int A[], int n){
	    for (int i = 0; i < n; i++){
	        if (A[i] == i+1) continue;
	 
	        while (A[i] >= 1 && A[i] <= n && A[i] != i+1 && A[A[i]-1] != A[i])
	            //swap(A[i], A[A[i]-1]);
	        	A[i] = A[i] ^ A[A[i]-1];
	        	A[A[i]-1] = A[i] ^ A[A[i]-1];
	        	A[i] = A[i] ^ A[A[i]-1];
	    }
	 
	    for (int i = 0; i < n; i++)
	        if (A[i] != i+1) return i+1;
	 
	    return n+1;
	}
	
	public static void main(String[] args) {
		System.out.println(divide(153,8));
		System.out.println(trappingRainWater(new int[]{0,1,0,2,1,0,1,3,2,1,2,1,2}));
		int[][] image = new int[3][3];
		image[0] = new int[]{1,2,3};
		image[1] = new int[]{4,5,6};
		image[2] = new int[]{7,8,9};
		rotateImage(image);
		TreeSet set = new TreeSet();
		System.out.println(firstMissingPositive(new int[]{1,1,0,-1,-2}));
	}

}
